struct PreciseCover { // 精确覆盖

using vi = vector<int>;

int solve(){
    dlx(0);
    return Ans;
}

/// 初始化，01矩阵尺寸为row * col
void init(int row_size, int col_size){
    Rth.assign((row_size + 1) * (col_size), 0);
    Cth.assign((row_size + 1) * (col_size), 0);
    Flag.assign((row_size + 1) * (col_size), 0);
    CCnt.assign((row_size + 1) * (col_size), 0);
    Up.assign((row_size + 1) * (col_size), 0);
    Down.assign((row_size + 1) * (col_size), 0);
    Left.assign((row_size + 1) * (col_size), 0);
    Right.assign((row_size + 1) * (col_size), 0);
    for(int i=0;i<col_size;++i){
        Right[Up[i] = Down[i] = Left[i + 1] = i] = i + 1;    
    }
    Right[Left[0] = Up[col_size] = Down[col_size] = col_size] = 0;
    toUsed = col_size;

    RHead.assign(row_size + 2, Ans = -1);
    RHead[0] = 0;
    AnsRows.assign(row_size, 0);
    return;
}

// row行col列设置为1
void link(int row, int col){
    ++CCnt[Cth[++toUsed] = col]; //指定所在列，并将该列元素个数加1
    Rth[toUsed] = row;           //指定所在行

    Down[toUsed] = Down[col];
    Up[Down[col]] = toUsed;
    Up[toUsed] = col;
    Down[col] = toUsed; //将节点插入列链表，本质就是链表的头插入

    if(RHead[row] < 0){ // 本行的第一个元素 
        RHead[row] = Left[toUsed] = Right[toUsed] = toUsed;
    }else{
        int const & h = RHead[row];
        Right[toUsed] = Right[h];
        Left[Right[h]] = toUsed;
        Right[Left[toUsed] = h] = toUsed; //将节点插入行链表，本质就是链表的头插入
    }
    return;
}

void remove(int node){
    Left[Right[Left[node]] = Right[node]] = Left[node];//将node从行链表中摘除

    //对每一个与node同列的节点i
    for(int i=Down[node];i!=node;i=Down[i]){
        //对每一个与节点i同行的节点j
        for(int j=Right[i];j!=i;j=Right[j]){
            Down[Up[Down[j]] = Up[j]] = Down[j];//将j从列链表中摘除
            --CCnt[Cth[j]];
        }
    }
}
//恢复node节点的同列节点
void resume(int node){
    Left[Right[node]] = Right[Left[node]] = node;
    for(int i=Up[node];i!=node;i=Up[i])for(int j=Left[i];j!=i;j=Left[j]){
        ++CCnt[ Cth[ Up[Down[j]] = Down[Up[j]] = j ] ];
    }
    return;    
}

//d已经删除的行数
bool dlx(int d){
    if(Right[0] == 0){
        Ans = d;
        return true;
    }

    int col, tmp = inf();
    //找到列元素最少的列
    for(int i=Right[0];i!=0;i=Right[i])
        if( CCnt[i] < tmp && 1 == ( tmp = CCnt[col=i] ) ) break;

    remove(col);

    //从第col列中，选择某一节点所在行进行删除
    for(int i=Down[col];i!=col;i=Down[i]){
        AnsRows[d] = Rth[i];
        for(int j=Right[i];j!=i;j=Right[j])remove(Cth[j]);
        if ( dlx(d+1) ) return true;
        for(int j=Left[i];j!=i;j=Left[j])resume(Cth[j]);
    }

    resume(col);
    return false;
}

void disp(){
    for(int i=0;i<=toUsed;++i){
        printf("(%d, %d, %d, %d)\n", Up[i], Down[i], Left[i], Right[i]);
    }   
    return;
}
static int inf(){
    static const int INF = 1000000;
    return INF;
}

// 上下左右
vi Up, Down, Right, Left;
// 所在行列
vi Rth, Cth;
// 每一行的头指针
vi RHead;
// 每一列元素的数量
vi CCnt;
// 答案
int Ans;
vi AnsRows;
int toUsed;
vi Flag;

}